#include <bits/stdc++.h>
using namespace std;

/*
2434. 使用机器人打印字典序最小的字符串
已解答
中等
相关标签
premium lock icon
相关企业
提示
给你一个字符串 s 和一个机器人，机器人当前有一个空字符串 t 。执行以下操作之一，直到 s 和 t 都变成空字符串：

删除字符串 s 的 第一个 字符，并将该字符给机器人。机器人把这个字符添加到 t 的尾部。
删除字符串 t 的 最后一个 字符，并将该字符给机器人。机器人将该字符写到纸上。
请你返回纸上能写出的字典序最小的字符串。

 

示例 1：

输入：s = "zza"
输出："azz"
解释：用 p 表示写出来的字符串。
一开始，p="" ，s="zza" ，t="" 。
执行第一个操作三次，得到 p="" ，s="" ，t="zza" 。
执行第二个操作三次，得到 p="azz" ，s="" ，t="" 。
示例 2：

输入：s = "bac"
输出："abc"
解释：用 p 表示写出来的字符串。
执行第一个操作两次，得到 p="" ，s="c" ，t="ba" 。
执行第二个操作两次，得到 p="ab" ，s="c" ，t="" 。
执行第一个操作，得到 p="ab" ，s="" ，t="c" 。
执行第二个操作，得到 p="abc" ，s="" ，t="" 。
示例 3：

输入：s = "bdda"
输出："addb"
解释：用 p 表示写出来的字符串。
一开始，p="" ，s="bdda" ，t="" 。
执行第一个操作四次，得到 p="" ，s="" ，t="bdda" 。
执行第二个操作四次，得到 p="addb" ，s="" ，t="" 。
 

提示：

1 <= s.length <= 105
s 只包含小写英文字母。
*/

// 法一
class Solution {
public:
    string robotWithString(string s) {
        // 贪心
        string ans;
        stack<char> sta;
        vector<int> cnt(26, 0);

        // 做一个遍历
        for (char ch : s) {
            cnt[ch - 'a']++;
        }

        int minStr = 0;
        for (char ch : s) {
            sta.push(ch);
            cnt[ch - 'a']--;
            while (minStr < 26 && cnt[minStr] == 0)     minStr++;
            while (!sta.empty() && (minStr >= 26 || sta.top() <= ('a' + minStr))) {
                ans.push_back(sta.top());
                sta.pop();
            }
        }
        return ans;
    }
};


// 法二
// 也是栈这一思路 自己使用三指针模拟栈
// 性能优于STL
class Solution {
public:
    string robotWithString(string s) {
        const int n = s.length();
        // 预处理：创建数组t存储从位置i到末尾的最小字符
        // 技巧：在s末尾添加哨兵字符'z'（确保比所有小写字母大）
        string t = s + 'z';  // 此时t长度为n+1
        
        // 逆向遍历：计算每个位置开始的最小字符
        // 思路：从后向前递推，t[i] = min(当前字符, 后续最小字符)
        for (int i = n - 1; i >= 0; i--) {
            t[i] = min(t[i], t[i + 1]);  // 当前位置的最小字符
        }
        
        // 结果字符串（初始化为s，但后续会覆盖）
        string res = s;
        // 三指针操作：
        // i: 遍历原字符串s (1~n)
        // j: 模拟栈顶指针（初始-1表示空栈）
        // k: 结果字符串的写入位置
        for (int i = 1, j = -1, k = 0; i <= n; i++) {
            // 操作1：从s取首字符压入栈t
            t[++j] = s[i - 1];  // j自增后压入字符
            
            // 操作2：当栈非空且栈顶<=后续最小字符时
            // 核心贪心策略：尽早弹出较小字符保证字典序最小
            while (j != -1 && t[j] <= t[i]) {
                res[k++] = t[j];  // 弹出栈顶写入结果
                j--;              // 栈指针下移
            }
        }
        return res;
    }
};